COMPRESSION DES DONNÉES

COMPRESSION DES DONNÉES

COMPRESSION DES DONNÉES

On peut chercher à rendre minimale la longueur d’un message en codant celui-ci. Si, après décodage, on retrouve exactement le message initial, on dit que le code est réversible, ou bijectif. Ce type de codage est nécessaire pour des messages de type textuel (il est évidemment interdit de perdre ou même d’altérer un caractère alphanumérique dans le cas, par exemple, de la transmission de données financières ou boursières, ou encore d’horaires d’avions). Dans la compression de données, toute perte d’information est donc interdite, à la différence du compactage de données.

De manière générale, pour la compression de données, la seule méthode utilisable pour réduire la longueur d’un message est de tenter de trouver un code dont la redondance soit aussi faible que possible (la redondance peut être définie comme l’action de fournir plus d’information qu’il n’en est nécessaire pour définir un objet, dans le but d’éviter l’ambiguïté ou l’erreur).

Une méthode très efficace de réduction de la redondance par un codage approprié a été proposée par David Albert Huffman au début des années 1950. Schématiquement, cette méthode consiste à faire une liste des n symboles utilisés dans le message dans l’ordre décroissant de leur probabilité d’apparition (fréquence d’apparition/nombre de symboles du message). On crée alors, à partir de cette liste, une deuxième liste en additionnant les probabilités d’apparition des deux derniers symboles de la liste initiale, en supprimant celles-ci, et en les remplaçant par leur somme. Cela fait, on ordonne cette nouvelle liste (qui comporte maintenant n – 1 symboles) et on recommence l’opération précédente sur cette nouvelle liste jusqu’à obtenir finalement une liste ne comportant plus que deux nombres. On affecte alors 1 à l’un des nombres et 0 à l’autre. On reprend ensuite les listes successives dans l’ordre inverse où elles ont été établies et, chaque fois qu’une probabilité d’une liste est la somme de deux probabilités d’une liste précédente, on affecte respectivement 1 et 0 à chacune des probabilités formant cette somme, jusqu’à ce qu’on revienne à la liste initiale des symboles. Pour chaque symbole, on aura alors son code binaire en juxtaposant les 1 et les 0 que l’on rencontre en allant de ce symbole jusqu’à la liste située à l’autre extrémité et qui ne comporte que deux nombres.

Le gain en temps de transmission apporté par le codage de Huffman est d’autant plus important que l’on connaît avec plus de précision la fréquence d’apparition de tous les symboles de l’alphabet utilisé, mais cela suppose qu’on explore une première fois le message pour dresser la liste des probabilités des symboles avant de déterminer le code de Huffman pour chaque symbole. Il en résulte que le destinataire ne peut connaître le code utilisé, puisque celui-ci dépend du message; il ne peut donc pas décoder le message. Il faut donc nécessairement faire précéder l’envoi du message d’un «en-tête» donnant le code de chaque symbole, ce qui a pour effet d’allonger le temps de transmission. On reperd ainsi, en partie ou en totalité (selon la longueur du message), le temps gagné grâce au codage de Huffman! Une solution consiste à utiliser une table de codage universelle établie une fois pour toutes pour la langue du message, ce qui évite l’envoi du code mais donne, en revanche, des gains extrêmement variables, pouvant aller jusqu’à des pertes, selon la teneur du message (textes littéraires, factures, dossiers médicaux, liste de statistiques, bulletins météorologiques, etc.).

Durant les vingt années qui ont suivi la parution de l’article de Huffman, l’essentiel des travaux dans ce domaine a porté sur diverses variantes de ce codage, et ce n’est qu’à partir de la publication, en 1977, d’un article de deux chercheurs israéliens, Abraham Lempel et Jacob Ziv, suivi en 1978 d’un nouvel article des deux mêmes chercheurs, que les travaux sur la compression, fondés sur ce que l’on a appelé l’algorithme LZ, d’après les noms des deux auteurs, ont pris un nouveau départ. Le principe qui sous-tend l’algorithme LZ est celui du codage à base de dictionnaire . Schématiquement, considérons un dictionnaire de 500 pages avec 100 mots par page. Pour coder un mot, on peut soit coder séparément chacune de ses lettres, auquel cas il faut 7 bits par lettre et, les mots en français ayant une longueur moyenne de 5 lettres, cela conduit à 35 bits par mot en moyenne, soit indiquer le numéro de la page (9 bits) et le numéro d’ordre du mot dans la page (7 bits), ce qui conduit à 16 bits pour coder n’importe quel mot du dictionnaire: on obtient ainsi un gain supérieur à 2.

Toutefois, ce mode de codage statique (dictionnaire fixe) serait peu commode car il faudrait stocker un dictionnaire de 50 000 mots dans la mémoire de l’ordinateur servant à coder (ou à décoder), ce qui prendrait une place considérable, sans parler de la lenteur du codage due au temps d’accès à cette masse importante de données pour chaque mot et sans compter qu’il faudrait changer de dictionnaire chaque fois que l’on change de langue.

En réalité, l’algorithme LZ est un algorithme adaptatif, c’est-à-dire qu’il construit pour chaque message un dictionnaire, qui est, à chaque instant, fonction de la partie du message qu’il a lue, en même temps qu’il utilise ce dictionnaire pour coder la suite du message. Cela entraîne un avantage supplémentaire puisque, du côté du destinataire, ce même algorithme est utilisable en décodage sans aucune information supplémentaire car l’algorithme est capable de reconstruire une copie exacte du dictionnaire de l’émetteur au fur et à mesure de la réception du message compressé.

Cet algorithme a rencontré presque immédiatement un grand succès puisque, un an seulement après sa publication, le logiciel Compress, initialement développé en langage C sur les ordinateurs Vax de Digital Equipment, était disponible pour toutes les machines sous système d’exploitation Unix, tandis qu’il devenait rapidement disponible sur les micro-ordinateurs, avec diverses variantes et sous différents noms, avec des taux de compression atteignant couramment et dépassant parfois 50 p. 100.

On a vu que la compression de données exigeait entre l’émetteur et le destinataire un minimum d’entente préalable sur les logiciels à utiliser, ce qui a pour effet de compliquer singulièrement les communications. Cette difficulté a conduit certains organismes (privés et publics) à proposer des normes qui soient indépendantes des utilisateurs. C’est ainsi que presque tous les modems sont équipés de puces assurant la compression de données au vol soit selon la norme MNP-5 (algorithme de Huffman adaptatif), soit selon la recommandation V-42 bis du Comité consultatif international télégraphique et téléphonique (C.C.I.T.T.; algorithme de type LZ), et les mettent en œuvre de manière automatique, c’est-à-dire sans aucune intervention des utilisateurs et même, à la limite, à leur insu.

Encyclopédie Universelle. 2012.